Packet transmission is characterized by the technique of disassembling, at the sending subscriber's end of a network, the data of the sending subscriber or user for insertion into separate bursts or packets and, at the other end of the network, reassembling the data from the packets for delivery to the receiving user. This type of transmission is especially useful in common carrier or time shared switching systems since the circuit or path resources required for the data transmission of the user need only be available while a packet is being forwarded through the network and such resources are therefore available to other users for their paths or circuits in the periods intervening the transmission of such packets.
The resources which may be shared in packet networks include transmission lines (i.e., transmission bandwidth), processors, ports and data or packet buffers. In large multinode networks, serving a plurality of geographically separated users, each node or packet switch accommodates many such ports terminating paths which extend to users and to other nodes. In addition, each node may include one or more processors which, among other functions, route and process packets through the node. Each node may further include many buffers for storing packets in anticipation of such routing or awaiting availability of an output port. Each line between nodes or extending to users may serve a plurality of "calls" and thus accommodate a corresponding plurality of paths or circuits. For such large networks, sharing such facilities results in substantial savings of the total amount of resources required for the system.
One of the problems in large packet transmission or packet switching networks arises when many users attempt to utilize the network at the same time. This results in the formation of many paths or circuits for routing the data and the resources become congested and thus unavailable to a user or to the user's packet when it is being forwarded through the network. It has been found that congestion tends to spread through the network, if uncontrolled, rendering the network unavailable to the various users.
In various previous studies of resource congestion it has been found that one of the principle areas of investigation is congestion of packet buffers, particularly where the buffers become unavailable to incoming packets. One solution of the packet buffer congestion problem is to halt all incoming traffic to the node on all incoming lines when the packet buffers become congested (filled) and no buffers are available for further incoming packets. This method is unsatisfactory since it not only stops incoming packets on heavily used paths but also stops incoming packets from users who originate only a small amount of data flow and therefore do not substantially contribute to buffer congestion.
Another method comprises a credit system which limits the data flow through each of the paths or circuits. One such credit system is termed an end-to-end flow control system wherein the ultimate terminating terminal issues a limited number of credits to the network corresponding to the number of packets that the terminal is willing to receive. Each node upon receiving (being granted) such a credit from a remote receiver unit terminating the node output path or circuit sends or grants a credit to the remote sender unit terminating the corresponding node input path or circuit. Accordingly, for each path, at any instant of time, the number of output credits should equal the sum of the number of input credits plus the number of packets presently being processed through the node. This credit system of receiving or being granted credits from the output path (called an output window mechanism) and granting credits to the input path (called an input window mechanism) results in limiting the data flow through the individual path or circuit to substantially reduce the possibility of buffer congestion in the node. The credit method, however, cannot guarantee freedom from buffer congestion and, at the same time, tends to reduce data flow to the point where the node resources are not amply utilized. In addition, since credits are advantageously carried by packets flowing in the reverse direction, a congested node may not be able to accept the credit carrying packets and may therefore remain indefinitely unavailable (deadlocked) with respect to granting credits to input paths.
Accordingly, it is an object of this invention to control data flow through a node to avoid congestion. It is a more specific object of this invention to utilize a data flow mechanism for each path or circuit which avoids node congestion while more fully utilizing node resources. It is an additional object of this invention to employ a credit mechanism which is not subject to network deadlock.